#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
 typedef int Elemtype;

 typedef struct LinkNode{
        Elemtype data;
        struct LinkNode*next;
 }LinkNode,*LinkList;


void createTail(LinkList * L,Elemtype arr[],int length){
    //分配空间，构建头结点
    (*L) = (LinkNode*) malloc(sizeof(LinkNode));
    (*L)->next = NULL;
    LinkNode * pCur = (*L); //最后一个节点的指针
    //遍历数组，给每一个新的元素分配新的节点，再尾插
    int cnt = 0;
    while (cnt < length)
    {
       LinkNode *pNode = (LinkNode*) malloc(sizeof(LinkNode));
       pNode->data = arr[cnt++];
       pNode->next = NULL;
       pCur->next = pNode;
       pCur = pCur->next;
    }
    
}

void createHead(LinkList * L,Elemtype arr[],int length){
    //分配空间，构建头结点
    (*L) = (LinkNode*) malloc(sizeof(LinkNode));
    (*L)->next = NULL;
    //遍历数组，给每一个新的元素分配新的节点，再头插
    int cnt = 0;
    while (cnt < length)
    {
       LinkNode *pNode = (LinkNode*) malloc(sizeof(LinkNode));
       pNode->data = arr[cnt++];
       pNode->next = NULL;

       pNode->next = (*L)->next;
       (*L)->next = pNode;
    }
    
}

 void print(LinkList L){
        LinkNode *pNode = L->next;
        while (pNode!=NULL)
        {
           printf(" %d ",pNode->data);
           pNode = pNode->next;
        }
        printf("\n");
 }
#define INF -9999999
 //求最大整数
 int Max(LinkNode * pNode){
    if(pNode ==NULL){
        return INF ;    
    }
    //迭代逻辑  比较返回来的值和我自己的值谁更大
    int res = pNode->data > Max(pNode->next) ?pNode->data : Max(pNode->next) ;
    return res;
 }
//求节点数
int Nodes(LinkNode * pNode){
    if(pNode ==NULL){
        return 0 ;    
    }
    //迭代逻辑  后面所有节点数 +1
    int res = Nodes(pNode->next) +1;
    return res;
 }
 
//求所有值之和
int Sum(LinkNode * pNode){
    if(pNode ==NULL){
        return 0 ;    
    }
    //迭代逻辑  后面所有节点之和 +本节点的值
    int res = Sum(pNode->next) + pNode->data;
    return res;
 } 
//求第i个数据节点
 LinkNode * findIth(LinkList L,int i){
    int cnt = 0;
    LinkNode* pNode = L;
    while (pNode->next !=NULL)
    {
        cnt++;
        if(i==cnt){
          return pNode->next;     
        }
        pNode = pNode->next;
    }
    

 }

 //在第i个数据节点前插入一个元素e
 void insertBeforeIth(LinkList L,int i,Elemtype e){
    int cnt = 0;
    LinkNode* pre = L;
    LinkNode *pCur = L->next;
    while (pCur!=NULL)
    {
        cnt++;
        if(i == cnt){
            LinkNode *pNode = (LinkNode*) malloc(sizeof(LinkNode));
            pNode->data = e;
            pNode->next = pCur;
            pre->next = pNode;
            break;
        }
        pre = pCur ;
        pCur = pCur->next;
    }
    
 }
//求倒数第m个位置节点并输出
//算法思想：
void getData(LinkList L,int m){
    LinkNode * pre = L->next; //pre最终指向倒数m位置
    LinkNode * pCur = L->next;
    int cnt = 1;
    while (pCur!=NULL)
    {
        if(cnt == 1+m){
            break;
        }
        pCur = pCur->next;
        cnt++;
    }// pCur 和 pre 相隔了m距离
    while (pCur!=NULL)
    {
       pCur = pCur->next;
       pre = pre->next;
    }
    printf(" the -mth is %d\n ",pre->data);
}
//求第i个节点的前驱
LinkNode * getPre(LinkList L,int i){
    int cnt = 0;
    LinkNode* pNode  = L;
    while (pNode->next!=NULL)
    {   //里面讨论的是pnode的后继而不是pnode本身
        cnt++;
        if(cnt == i){
            //pnode->next 是第i号
            return pNode;
        }
        pNode = pNode->next;
    }
}
//两表移植问题
void operateAandB(LinkList A,LinkList B,int j,int len){
        //先增加头结点便于操作
        LinkNode* pLa = (LinkNode*)malloc(sizeof(LinkNode));
        LinkNode* pLb = (LinkNode*)malloc(sizeof(LinkNode));
        pLa->next = A;
        pLb->next = B;
        //使用前面的求前驱函数，求得必须使用的几个指针
        LinkNode *Lapre = getPre(pLa,j);
        LinkNode *Lbpre = getPre(pLb,j);
        LinkNode *Lalength = getPre(pLa,j+len);
        //移动，从a移植到b
        LinkNode *p = Lapre->next;//len的开始，临时记录下来，后面Lapre的next会发生变化
        Lapre->next = Lalength->next;
        Lalength->next = Lbpre->next;
        Lbpre->next = p;
        //打印结果
        print(pLa);
        print(pLb);
        //释放头结点
        free(pLa);
        free(pLb);
}
//判断前半段和后半段是不是相同/对称
int isSym(LinkList L,int n){
    int cnt = 1;
    LinkNode * pNode = L->next;
    //移动找到后半部分的起始位置的指针
    while (pNode!=NULL)
    {
        if(cnt == n/2){
            break;
        }
        cnt++;
        pNode = pNode->next;
    }
    LinkNode *pFront = L->next;
    LinkNode *pLast = NULL;
    //根据n的奇偶确定后半段起始位置的指针
    if(n%2 == 0){
        pLast = pNode->next;
    }else{
        pLast = pNode->next->next;
    }
    //一起移动比较是否相同
    while (pLast !=NULL)
    {
       if(pFront->data != pLast->data){
            return 0;
       }
       pFront = pFront->next;
       pLast = pLast->next;
    }
    return 1;
}
//删除非递减链表中重复元素
void deleteSimilar(LinkList L){
    LinkNode * pre = L;
    LinkNode * pCur = L->next;
    while (pCur != NULL)
    {
       if( pre!=L && pre->data == pCur->data){
            //删除
            pre->next = pCur->next;
            free(pCur);
            pCur = pre->next;
       }else{
        pre = pCur;
        pCur = pCur->next;
       }
    }
}

//非递减，统计比x小的元素个数
int lessXnodes(LinkList L,Elemtype x){
    LinkNode * pre = L;
    LinkNode * pCur = L->next;
    int cnt = 0;
    while (pCur != NULL && pCur->data < x)
    {   //只需要考虑不重复的计数
       if( pre==L || pre->data != pCur->data){
            //计数
           cnt++;
           pre = pCur;
           pCur = pCur->next;
       }else{
            //重复
            pCur = pCur->next;
       }
    }
    printf("the res is %d\n",cnt);
    return cnt;

}
//非递减，删除A表中和B表相同的元素
void deleteAandBSame(LinkList La,LinkList Lb){
    LinkNode *pre = La;
    LinkNode* paCur = La->next;
    LinkNode* pbCur = Lb->next;

    while (paCur!=NULL && pbCur!=NULL)
    {
        if(paCur->data > pbCur->data){
            pbCur = pbCur->next;

        }else if (paCur->data < pbCur->data)
        //  要保证pre和paCur相邻，一起移动
        {   pre = pre->next;
            paCur = paCur->next;
        }else{
            //相等就删除
            pre->next = paCur->next;
            free(paCur);
            paCur = pre->next;
        } 
    }
}
//在表Lc中删除同时出现在La和Lb中的元素
/**
 * 寻找La和Lb相同的元素
 *      在表C中寻找该元素并删除
 */
void deleteAandBandCSame(LinkList La,LinkList Lb,LinkList Lc){
    LinkNode *pre = Lc;
    LinkNode* pcCur = Lc->next;
    LinkNode* paCur = La->next;
    LinkNode* pbCur = Lb->next;

    while (paCur!=NULL && pbCur!=NULL)
    {
        if(paCur->data > pbCur->data){
            pbCur = pbCur->next;
        }else if (paCur->data < pbCur->data)
        {  
            paCur = paCur->next;
        }else{
            //相等在C中寻找，找到就删除
           while (pcCur !=NULL && paCur->data >= pcCur->data)
           {
                if(paCur->data == pcCur->data){
                    pre->next = pcCur->next;
                    free(pcCur);
                    pcCur = pre->next;
                    break; // 因为只有一个这样的元素删掉之后不用再往后面遍历寻找了
                }
                pre = pcCur;
                pcCur = pcCur->next;
           }
           // La Lb一起移动
           paCur = paCur->next;
           pbCur = pbCur->next;
        } 
    }
}   
//保证去重的尾插，如果待插入的节点和当前最后一个节点值相同就不插入
void insertTail(LinkNode **pcLast, LinkNode * pNode){
    if(pNode->data != (*pcLast)->data){
        pNode->next = NULL;
         (*pcLast)->next = pNode;
         (*pcLast) = pNode;
    }
}

//将A表和B表合并成C表并去重
void merge(LinkList La,LinkList Lb,LinkList *Lc ){
    //使用A或者B的头部作为C的头结点
    LinkNode* paCur = La->next;
    LinkNode* pbCur = Lb->next;
    *Lc = La;
    LinkNode *pcCur = *Lc;//最后一个节点
    free(Lb);
       //使用最小值法进行尾插
    /**
     * 对比LA和LB，大小关系，如果有一方小，那么这个节点就可能插入C，然后谁小谁移动，
     *      如果相等的话，选一个进行插入C
     * 
     * 在插入C之前要进行比较，保证插入的和之前的不重复
     * 如果有一个表没有插入完成就把剩下的都插入就可以了
     */
    while (paCur!=NULL && pbCur!=NULL)
    {   LinkNode *tempNode = NULL;
       if(paCur->data > pbCur->data){
            tempNode = pbCur;
            pbCur = pbCur->next;
            insertTail(&pcCur,tempNode);
            /**
             *  if(pNode->data != pcCur->data){
                pNode->next = NULL;
                pcCur->next = pNode;
                pcCur = pNode;
                }
             */
       }else if(paCur->data < pbCur->data){
            tempNode = paCur;
            paCur = paCur->next;
            insertTail(&pcCur,tempNode);
       }else{
            LinkNode *tempBNode = pbCur;
            tempNode = paCur;
            paCur = paCur->next;
            pbCur = pbCur->next;
            free(tempBNode);
            insertTail(&pcCur,tempNode);
       }
    }
    while (paCur!=NULL)
    {
        LinkNode * tempNode = paCur;
        paCur = paCur->next;
       insertTail(&pcCur,tempNode);
    }

    while (pbCur!=NULL)
    {
        LinkNode * tempNode = pbCur;
        pbCur = pbCur->next;
        insertTail(&pcCur,tempNode);
    }
}
//递增单链表删除属于min-max的元素
void deleteNodes(LinkList L,int min ,int max){
    LinkNode *pre = L;
    LinkNode *pCur= L->next;
    while (pCur!=NULL && pCur->data < max)
    {
        if (pCur->data > min)
        {
           pre->next = pCur->next;
           free(pCur);
           pCur = pre->next;
        }else{
            pre = pCur;
            pCur = pCur->next;
        }
    }
}
/**
 * 冒泡排序
 *      1.相邻元素交换  
 *      2.有终点  顺序表n-1次，如果一开始就是有序的表， flag ： int isExchanged = 0; 
 *          只要进行了交换的操作，那就改变标志位 变为1，通过判断flag来看是否需要继续
 */
//冒泡排序升序  5(a) 5(b)
void bubbleSort(LinkList L){
    while (1)
    {
        int isExchanged = 0;
        LinkList pCur = L->next;
        while (pCur->next !=NULL)
        {
           if(pCur->data > pCur->next->data){
                Elemtype temp = pCur->data;
                pCur->data = pCur->next->data;
                pCur->next->data = temp;
                isExchanged = 1;
           }
           pCur = pCur->next;
        }
        if(!isExchanged){
            break;
        }
    }
}

//插入排序并去重
/**
 *  将未排序的序列元素 插入到  有序的序列中
 */
void insertSort(LinkList L){
    LinkNode *pCur = L->next; // 该指针是指向了未排序的序列的元素
    L->next =NULL;
    while (pCur !=NULL)
    {   //每一个循环都是为了插入一个元素
        LinkNode *pre  = L;
        LinkNode *pL = L->next;
        while (pL!=NULL)
        {   //找插入位置
           if(pL->data > pCur->data){
                break;
           }
           //当pL小于等于时候移动
           pre = pL;
           pL = pL->next;
        }
        //找到位置进行插入
        LinkNode *pNode  = pCur;
        pCur = pCur->next;

        // 1.不重复的 2. 待插入的元素比现在所有元素都小
        if(pre == L ||pre->data!=pNode->data){
            pNode->next = pL;
            pre->next = pNode;
        }else{
          free(pNode);  
        }
    }
}
//把小于x移动到x之前，大于x移动到x之后
void move(LinkList L,Elemtype x){
    //将头部断开，连接新的结果链表
    LinkNode *pCur = L->next;
    L->next = NULL;
    //定义一个X虚拟节点，便于之后插入所有的小于x和大于x的节点。该节点最后要被删掉
    LinkNode *pX = (LinkNode*)malloc(sizeof(LinkNode));
    pX->data = x;
    pX->next = NULL;
    //把虚拟节点插入结果链表中，定义一个prex指针，用于指向虚拟x的前驱，
    //之后删除或者当待插入节点是x本身时候用到
    L->next = pX;
    LinkNode* preX = L;
    LinkNode*pTail = pX;
    //对待处理数据节点进行遍历并比较和x的大小关系
    while (pCur!=NULL)
    {
        LinkNode*pNode = pCur;
        pCur = pCur->next;
        if (pNode->data < x)
        {
           //小于x，在虚拟节点之前进行头插。注意prex永远指向虚拟节点的前驱
           pNode->next = L->next;
           L->next = pNode;
           if(preX ==L){
             //如果prex等于L，就在头插之后进行移动
                preX=   preX->next;
           }
        }else if(pNode->data > x){
            //大于x，在虚拟节点之后使用尾插
            pNode->next = NULL;
            pTail->next = pNode;
            pTail = pNode;
        }else{
        //等于x，使用prex指针把真正的x节点放在虚拟节点的前面
        preX->next = pNode;
        pNode->next = pX;
        preX = preX->next;
        }
    }
    //删除虚拟节点
    preX->next = pX->next;
    free(pX);
}
//判断Lb（短链）是不是La(长链)的指针
int isSubLink(LinkList La, LinkList Lb){
    //定义Pla,Plb,start,start 指向每一个子链的开始位置便于pLa每次初始化
    LinkNode *pLa = La->next;
    LinkNode *pLb = Lb->next;
    LinkNode *start = pLa;
    //遍历环节，当a和b有一个遍历结束就不用遍历
    while (pLa !=NULL && pLb!= NULL)
    {
       if(pLa->data == pLb->data ){
            pLa = pLa->next;
            pLb = pLb->next;
       }else{
        //让start始终指向下一个子链的开始
            start = start->next;
            pLa = start;
            pLb = Lb->next;
       }
    }
    //如果b走完，那么就是子链
    //如果a先走完了，那么就不是子链
    if(pLb == NULL){
        return 1;
    }
    return 0;
}
//求链表长度
int getLen(LinkList L){
    LinkNode * pNode = L->next;
    int len = 0;
    while (pNode!= NULL)
    {
        len ++;
        pNode = pNode->next;
    }
    return len;
    
}

//求共享节点的位置
LinkNode* getSharedNode(LinkList La,LinkList Lb){
    LinkNode * pLa = La->next;
    LinkNode * pLb = Lb->next;

    //求长度
    int LenA = getLen(La);
    int LenB = getLen(Lb);

    int cnt = 0 ;
    if(LenA > LenB){
        while (cnt < (LenA - LenB))
        {
           pLa = pLa->next;
           cnt++;
        }
    }else{
          while (cnt < (LenB - LenA))
        {
           pLb = pLb->next;
           cnt++;
        }   
    }
    while (pLa != pLb)
    {
        pLa = pLa->next;
        pLb = pLb->next;
    }
    return pLa;

} 

/**
 * 1. 找到后半段的位置
 * 2. 将后半段逆置
 * 3. 前半段和后半段逆置 依次尾插
 */
void convertLinkList(LinkList L,int n){
    LinkNode *preNode = L->next;
    LinkNode * pLastNode = NULL;
    int cnt = 0;
    LinkNode *pCur = L;
    while (pCur->next != NULL)
    {
        cnt ++;
        if(cnt > n/2){
            break;
        }
        pCur = pCur->next;
    }
    pLastNode = pCur->next;
    //这样可以使得前半段有结束条件
    pCur->next = NULL;
    //后半段逆置
    L->next = NULL;
    while (pLastNode != NULL)
    {
        LinkNode *pNode = pLastNode;
        pLastNode = pLastNode->next;
        pNode->next = L->next;
        L->next = pNode;
    }
    pLastNode = L->next;
    L->next = NULL;
    pCur = L; // 用于指向最后一个节点，便于尾插的操作
    //执行交互依次尾插
    while (pLastNode !=NULL && preNode != NULL)
    {
        //每个循环要插入一对
        //从前半段拿
        LinkNode *pNode = preNode;
        preNode = preNode->next;
        pCur->next = pNode;
        pCur = pNode;
        //从后半段拿
        pNode = pLastNode;
        pLastNode = pLastNode->next;
        pCur->next = pNode;
        pNode->next = NULL;
        pCur = pNode;
    } 
    pCur->next = pLastNode;
}

//创建带头循环单链表
void createCircleTail(LinkList * L,Elemtype arr[],int length){
    //分配空间，构建头结点
    (*L) = (LinkNode*) malloc(sizeof(LinkNode));
    (*L)->next = (*L); // 头部的下一个还是自己
    LinkNode * pCur = (*L); //最后一个节点的指针
    //遍历数组，给每一个新的元素分配新的节点，再尾插
    int cnt = 0;
    while (cnt < length)
    {
       LinkNode *pNode = (LinkNode*) malloc(sizeof(LinkNode));
       pNode->data = arr[cnt++];
       pNode->next = pCur->next; // 完成尾部到头部的连接
       pCur->next = pNode;
       pCur = pCur->next;
    }
    
}
//循环单链表的打印
void printCLink(LinkList L){
     LinkNode *pNode = L->next;
        while (pNode!=L)
        {
           printf(" %d ",pNode->data);
           pNode = pNode->next;
        }
        printf("\n");
}
//循环单链表的打印
void printCLink02(LinkList L){
        LinkNode *pNode = L;
        printf(" %d ",pNode->data);
        pNode = pNode->next;
        while (pNode!=L)
        {
           printf(" %d ",pNode->data);
           pNode = pNode->next;
        }
        printf("\n");
}
//逆置循环单链表
void reverseCLink(LinkList L){
    LinkNode *pCur = L->next;
    L->next = L;
    while (pCur != L)
    {
        LinkNode *pNode = pCur;
        pCur = pCur->next;
        pNode->next = L->next;
        L->next = pNode;
    }   
}
//将循环单链表左移k，此处使用的是不带头节点的循环链表
void moveK(LinkList* L, int k ){
    int cnt = 0;
    LinkNode * pNode =*L;
    while (cnt < k)
    {
        pNode = pNode->next;
        cnt++;
    }
    (*L) = pNode;
}

void deletePnodePre(LinkNode *p){
    LinkNode *pre = p;
    LinkNode * pCur = p->next;

    while (pCur->next != p)
    {
        pre= pCur;
        pCur = pCur->next;
    }
    //找到了直接前驱
    pre->next = pCur->next;
    free(pCur);
}

LinkList createCLink(){
        LinkList L = (LinkNode*)malloc(sizeof(LinkNode));
        L->next = L;
        return L;
}
//如果使用尾插，那就传最后一个数据节点的指针给L
void insertCLink(LinkList L,LinkNode* pNode){
    pNode->next = L->next;
    L->next = pNode;
}

void splitCLink(LinkList L){
    LinkList charLink = createCLink();
    LinkList numLink = createCLink();
    LinkList otherLink = createCLink();
    LinkNode * pCur = L->next;
    while (pCur!= L)
    {
        LinkNode * pNode = pCur;
        pCur = pCur->next;
        if(pNode->data >= 'A' && pNode->data <= 'z'){
            insertCLink(charLink,pNode);
        }else if(pNode->data >= '0' && pNode->data <= '9'){
            insertCLink(numLink,pNode);
        }else{
             insertCLink(otherLink,pNode);
        }
    }
}

//将单链表的第i号到第m号转为逆置的循环单链表
LinkList reverse(LinkList L,int i,int m){
    LinkNode *iPre = getPre(L,i);
    LinkNode * mPre = getPre(L,m);
    LinkNode * mLast = mPre->next->next;//m号节点的下一个节点，为了保证原本链表的完整性
    mPre->next->next = NULL;
    //拿到i-m段
    LinkNode * pNode = iPre->next;//拿到了第一个节点
    //从原链表删除i-m
    iPre->next = mLast;
    LinkList L2 = (LinkNode*)malloc(sizeof(LinkNode));
    L2->next = L2;
    while (pNode!=NULL)
    {
       //构建一个循环单链表，使用头插
       LinkNode * pCur = pNode;
       pNode = pNode->next;
       pCur->next = L2->next;
       L2->next = pCur;
    }
    return L2;
}

//将带头节点的循环单链表LA，LB，长度分别为m,n，合并为一个循环单链表，时间复杂度最小
LinkList combineCLink(LinkList La,LinkList Lb,int m,int n){
    LinkNode * pCur = NULL;
    if(m>n){
        //遍历短的链表，把短的链表的连在长的链表的头部
        pCur = Lb->next;
        while (pCur!=Lb)
        {
           LinkNode * pNode = pCur;
           pCur = pCur->next;
           pNode->next = La->next;
           La->next = pNode;
        }
        free(pCur);
        return La;
    }else{
        //现在a表是短的那个
        pCur = La->next;
        while (pCur!=La)
        {
           LinkNode * pNode = pCur;
           pCur = pCur->next;
           pNode->next = Lb->next;
           Lb->next = pNode;
        }
        free(pCur);
        return Lb;
    }
}


//创建尾指针指向的循环单链表
void createCircleTail02(LinkList * L,Elemtype arr[],int length){
    //分配空间，构建头结点
    (*L) = (LinkNode*) malloc(sizeof(LinkNode));
    (*L)->next = (*L); // 头部的下一个还是自己
    LinkNode * pCur = (*L); //最后一个节点的指针
    //遍历数组，给每一个新的元素分配新的节点，再尾插
    int cnt = 0;
    while (cnt < length)
    {
       LinkNode *pNode = (LinkNode*) malloc(sizeof(LinkNode));
       pNode->data = arr[cnt++];
       pNode->next = (*L)->next; // 完成尾部到头部的连接
       (*L)->next = pNode;
       (*L) = pNode;
    }
    
}
//打印尾指针指向的循环单链表
void printClink03(LinkList L){
    LinkNode* pHead = L->next;
    LinkNode * pNode = pHead->next;
    while (pNode != pHead)
    {
        printf(" %d ",pNode->data);
        pNode = pNode->next;
    }
        printf("\n");
    
}

void combineCLinkNewStruct(LinkList La,LinkList Lb){
        LinkNode * pAHead = La->next; //表A的头结点
        LinkNode* pBHead = Lb->next; //表B的头结点
        LinkNode* pNode = pAHead->next; //表A的第一个数据节点
        La->next = pBHead->next;
        pBHead->next = pNode;
        free(pAHead);

}

//双向链表的定义
typedef struct DuLinkNode{
    Elemtype data;
    struct DuLinkNode * pre;
    struct DuLinkNode * next;
}DuLinkNode,*DuLinkList;

//将双链表的next指针保持不变，但是pre方向变成一个升序的结构
void order(DuLinkList Dul){
    DuLinkNode * pData = Dul->next; //把数据节点保存下来了
    Dul-> next = NULL;
    //从pre方向使用一个插入排序，pre 从小到大
    
    while (pData != NULL)
    {
        //每次循环给一个待排序的数据找到位置并插入
        DuLinkNode * pre = Dul;// pre->pre == pCur
        DuLinkNode * pCur = Dul->pre; //把所有的pre当做单链表的next
        DuLinkNode *pNode = pData;
        pData = pData->next;
        //寻找位置
        while (pCur!= NULL && pCur->data < pNode->data)
        {
           pre = pCur;
           pCur = pCur->pre; //把所有的pre当做单链表的next
        }
        //pCur已经走到末尾了或者走到了第一个 大于等于pnode值的位置，那么pCur的前面就是该插入的位置
       pNode->pre = pre->pre;
       pre->pre = pNode;//执行插入操作
    }
}

//循环双链表的分割和逆置
void reverseDulCircleLink(DuLinkList L){
    DuLinkNode * L2 = (DuLinkNode *)malloc(sizeof(DuLinkNode)); //用于偶数段的头结点
    DuLinkNode * pData = L->next; //拿到所有的数据节点
    L2->next = L2;
    L2->pre = L2;
    L->next = L;
    L->pre = L;
    DuLinkNode *pTail = L;//用于尾插永远指向最后一个节点
    //分割成奇数和偶数段
    int isEven = 0; // 0是奇数位 ，1就是偶数位
    while (pData!=L)
    {   //根据pnode属于奇数还是偶数段决定插入到哪个链表当中
        DuLinkNode *pNode = pData;
        pData = pData->next;
        if (isEven == 0)
        { //奇数位  使用尾插
           pNode->next = pTail->next;
           pTail->next = pNode;
           pNode->pre = pTail;
           pTail = pNode;
           isEven = 1;
        }else{
         //偶数位 + 逆置偶数段使用头插
        pNode->next = L2->next;
        L2->next->pre = pNode;
        L2->next = pNode;
        isEven = 0;
        } 
    }
    //连接
    if(L2->next!=L2){
    pTail->next = L2->next;
    L2->next->pre = pTail;
    L2->pre->next = L;
    L->pre = L2->pre;
    }
}



 int main(){
    LinkList La,Lb,Lc,Ld;
    
    int a[10] = {1,2,3,4,5,6,7,8,9};
    int b[10] = {14,6,6,0,1,2};
    int c[10] = {1,2,3,4};
    createCircleTail02(&La,a,9);
    createCircleTail02(&Lb,b,6);
    createCircleTail(&Lc,c,4);

   //print(Lc);
//    LinkNode* res = getSharedNode(Lb,Lc);
//    printf("res is %d\n",res->data);
  //  convertLinkList(La,9);
//   reverseCLink(La);
   // deletePnodePre(La->next->next);
    //printCLink(combineCLink(La,Lc,9,4));
    combineCLinkNewStruct(La,Lb);
    printClink03(Lb);
  
 }